Network Security Cryptography Hash MAC

John

Network Security

Symmetric Cryptography

Sections: 2.1 Basics of Crypto | 2.2 Stream Ciphers & Adversaries | 2.3 Block Ciphers | 2.4 Hash Functions | 2.5 MAC and Authenticated Encryption

2.1 Basics of Cryptography

Goals of Cryptography

Primary Goal: Ensuring security of communication over an insecure medium

What Does Secure Communication Mean?

  • Confidentiality (Privacy/Secrecy): Only the intended recipient can see the communicated message
  • Integrity (Authenticity): The communication is generated by the alleged sender
  • Availability: Typically out of scope for cryptography (handled by other security mechanisms)
Insecure Medium: A communication channel where a man-in-the-middle adversary can eavesdrop, intercept, or manipulate messages

Symmetric (Private-Key) Cryptography

In symmetric cryptography, Alice and Bob share the same private key for both encryption and decryption.

Key Capabilities

  • Confidential Message Transmission:
    • One-time Pad
    • Stream Ciphers
    • Block Ciphers
  • Authenticated Message Transmission:
    • Message Authentication Codes (MACs)

Historical Context: Substitution Ciphers

General Substitution Cipher

Key Space: All permutations of Σ = {A, B, C, …, Z}
Encryption: Each letter X in plaintext P is replaced with π(X)
Decryption: Each letter Y in ciphertext is replaced with π⁻¹(Y)
Example:
Alphabet: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
π = B A D C Z H W Y G O Q X S V T R N M L K J I P F E U

Plaintext: BECAUSE → Ciphertext: AZDBJSZ

Strength and Weakness

  • Strength: Key space size is 26! ≈ 4×10²⁶ (difficult exhaustive search)
  • Historical Significance: Dominated secret writing throughout the first millennium A.D.
  • Critical Weakness: Vulnerable to frequency analysis
    • Languages have characteristic letter frequencies
    • Substitution ciphers preserve these statistical features
    • Attackers can use letter frequency patterns to break the cipher

One-Time Pad

Setup:
• Plaintext space = Ciphertext space = Key space = {0,1}ⁿ
• Key is chosen uniformly at random
• Key length equals message length

Operation

Encryption: Ciphertext = Plaintext ⊕ Key
Decryption: Plaintext = Ciphertext ⊕ Key
Example:
Plaintext: 11011011
Key: 01101001
Ciphertext: 10110010 (Plaintext ⊕ Key)

Decryption: 10110010 ⊕ 01101001 = 11011011 ✓

Shannon (Information-Theoretic) Security

Perfect Secrecy: Ciphertext reveals no information about plaintext

Formal Definition: Given any ciphertext, each plaintext of the same length is equally likely

Security Level: Secure even against adversaries with unbounded computational resources

One-Time Pad achieves perfect secrecy!

Critical Requirements for One-Time Pad

Key Randomness:

  • Key must be truly random (not pseudo-random)
  • Using text from a book as a key is NOT one-time pad and can be broken

Key Reuse Prohibition:

  • Key must NEVER be reused
  • Reusing a key creates a “Two-Time Pad” which is completely insecure
  • We’ll see attack examples later in wireless communication security

The “Bad News” Theorem

Theorem: Perfect secrecy ⇒ key-length ≥ message-length

Proof Intuition: To associate each possible plaintext with a ciphertext while maintaining perfect secrecy, we need at least one distinct key per plaintext.

Implication: Perfect secrecy comes at the cost of key management – you need as much secret key material as you have message data.

2.2 Stream Ciphers & Adversarial Models

Stream Ciphers Overview

Core Idea: Replace “truly random” with “pseudo-random”

Use a Pseudo-Random Number Generator (PRNG) to expand a short random seed into a long keystream

PRNG Functionality

PRNG: {0,1}ˢ → {0,1}ⁿ
(where s << n)
  • Input: Short (e.g., 128-bit) truly random seed
  • Output: Long string that “looks random”
  • Secret Key: The seed itself
  • Encryption: Ekey[M] = M ⊕ PRNG(key)

Pseudorandom Generator (PRG) Properties

A PRG is a deterministic algorithm that:

  • Receives a short truly random seed as input
  • Stretches it into a long string that is pseudorandom
  • Produces output that is computationally indistinguishable from truly random

Key Property: Adversary with bounded computational resources cannot distinguish PRG output from truly random output

Stream Cipher Examples

  • Based on: Hash functions, HMAC, block ciphers
  • Historical (Broken): RC4-based PRG (widely used, but now broken)
  • Modern (Potentially Good): Salsa20, ChaCha20

Properties of Stream Ciphers

Performance

  • Typical stream ciphers are very fast
  • Efficient for real-time communication

Usage Concerns

Widely used but often incorrectly implemented:

  • Content Scrambling System (CSS): Uses Linear Feedback Shift Registers incorrectly
  • Wired Equivalent Privacy (WEP): Uses RC4 incorrectly

Security Analysis

Under known plaintext, chosen plaintext, or chosen ciphertext attacks:

  • Adversary can learn the keystream (PRNG(key))
  • Security depends entirely on PRNG unpredictability
  • Does NOT have perfect secrecy (computational security only)

Adversarial Models for Ciphers

Base Assumptions:

  • The language of the plaintext is known to the adversary
  • The nature of the cipher is known to the adversary

Attack Models (Increasing Power)

Attack Type Adversary Capabilities Security Level
Ciphertext-Only Knows only ciphertexts Weakest adversary
Known-Plaintext Knows some plaintext-ciphertext pairs Moderate adversary
Chosen-Plaintext (CPA) Can choose messages and obtain their ciphertexts Minimum required security today
Chosen-Ciphertext Can choose ciphertexts and obtain their plaintexts Strongest adversary

Chosen-Plaintext Attack (CPA) – Detailed

Real-World Scenario: ATM & Bank

  1. Crook #1 changes PIN to a number of his choice (chosen plaintext)
  2. PIN is encrypted and transmitted: cipher(key, PIN)
  3. Crook #2 eavesdrops and learns the ciphertext
  4. Repeat for multiple PIN values to build a database

The CPA Security Game

Game Rules:

  1. Attacker does not know the secret key
  2. Attacker chooses as many plaintexts as desired and receives corresponding ciphertexts
  3. When ready, attacker picks two plaintexts M₀ and M₁
  4. Attacker is even allowed to pick plaintexts for which they previously learned ciphertexts
  5. Attacker receives either ciphertext of M₀ or ciphertext of M₁
  6. Attacker wins if they can correctly guess which one

Semantic Security Definition

Semantic Security (Ciphertext Indistinguishability):
Given a ciphertext (and length) of some unknown message, adversary cannot learn any additional information about the message that can be feasibly extracted

Formal Game: If adversary chooses two messages M₀ and M₁, and is given EK[Mb] where b is randomly chosen from {0,1}, the adversary has little advantage in guessing b

Important Security Result

Any deterministic or stateless encryption scheme is insecure against chosen-plaintext attacks

This is why encryption needs randomness (e.g., random IVs in block cipher modes)

Real Weaknesses of Stream Ciphers

These are fundamental weaknesses that exist even with strong PRNGs:

1. Key Stream Reuse

  • If the same stream is ever used twice, the cipher becomes easy to break
  • “Two-Time Pad” is completely insecure
  • Reason: C₁ ⊕ C₂ = (M₁ ⊕ K) ⊕ (M₂ ⊕ K) = M₁ ⊕ M₂ (key cancels out!)

2. Malleability

  • Stream ciphers are highly malleable
  • Easy to modify ciphertext so plaintext changes predictably
  • Example: Flipping bit i in ciphertext flips bit i in plaintext
  • Which security property is violated? Integrity!

Computational vs. Perfect Secrecy

Aspect Perfect Secrecy Computational Security
Security Against Unbounded adversary Polynomially-bounded adversary
Can Be Broken By Cannot be broken Brute force (trying all keys)
Key Length ≥ message length Fixed (e.g., 128, 256 bits)
Examples One-Time Pad Stream ciphers, block ciphers
Practical? Difficult (key distribution) Yes (foundation of modern crypto)

Proving Computational Security

Approach:

  1. Assume that certain problems are hard (require significant computational resources)
  2. Show that breaking security implies solving the hard problem
  3. Therefore, if the problem is hard, the scheme is secure

Computational security is the foundation of modern cryptography!

2.3 Block Ciphers

Why Block Ciphers?

Two Approaches to Defeating Frequency Analysis:

  1. Stream Ciphers: Use different keys in different locations
  2. Block Ciphers: Make the unit of transformation larger – encrypt block by block rather than letter by letter

Data Encryption Standard (DES)

Historical Background

  • Designed by IBM with modifications proposed by the National Security Agency (NSA)
  • US national standard from 1977 to 2001
  • Was the de facto standard for symmetric encryption

DES Specifications

  • Block size: 64 bits
  • Key size: 56 bits
  • Rounds: 16
  • Design focus: Hardware implementations

DES Security Status

Considered insecure now

  • Vulnerable to brute-force attacks (56-bit key is too small)
  • Vulnerable to differential cryptanalysis
  • Vulnerable to linear cryptanalysis

Advanced Encryption Standard (AES)

Development Process

  • In 1997, NIST called for algorithms to replace DES
  • Requirements: Unclassified, publicly disclosed, available royalty-free worldwide
  • Goal: Replace DES for government and private-sector encryption
  • October 2, 2000: Rijndael selected as AES (by Joan Daemen and Vincent Rijmen)

AES Requirements

  • Symmetric key cryptography as a block cipher
  • Minimum block size: 128 bits
  • Key sizes: 128, 192, and 256 bits

AES Features

Feature Specification
Design Goal Efficient in both hardware and software across various platforms
Block Size 128 bits (fixed)
Key Sizes 128, 192, or 256 bits (variable)
Rounds 10 (128-bit key)
12 (192-bit key)
14 (256-bit key)
Security Status No known practical weaknesses

Encryption Modes

The Need for Encryption Modes:
A block cipher encrypts only one block. We need methods to:

  • Extend encryption to arbitrarily long messages
  • Ensure that if the block cipher is secure, the encryption is secure
  • Provide semantic security (ciphertext indistinguishability)

Electronic Code Book (ECB) Mode

Operation

  • Message is broken into independent blocks
  • Each block is encrypted individually with the same key

Properties

Critical Weaknesses:

  • Deterministic: Same plaintext block → same ciphertext block
  • Pattern Preservation: Reveals data patterns when blocks repeat
  • No Integrity: Blocks can be mixed, matched, or reordered
  • Same Key Usage: Same message encrypted the same way every time
Usage Recommendation: NOT recommended for encrypting more than one block of data

Breaking Semantic Security with ECB

CPA Attack on ECB:

  1. Adversary requests encryption of M₀
  2. Adversary requests encryption of M₁
  3. In challenge phase, receives either E(M₀) or E(M₁)
  4. Adversary compares with previous encryptions to determine which message
  5. Attack succeeds because ECB is deterministic!

Cipher Block Chaining (CBC) Mode

Operation – Encryption

Initialization Vector (IV): Random, sent with ciphertext
C₀ = IV
Cᵢ = Ekey(Pᵢ ⊕ Cᵢ₋₁) for i = 1, 2, …, n

Operation – Decryption

Pᵢ = Dkey(Cᵢ) ⊕ Cᵢ₋₁

Properties

Advantages:

  • Randomized Encryption: Same plaintext → different ciphertext (due to random IV)
  • Dependency: Each ciphertext block depends on all preceding plaintext blocks
  • Semantic Security: Can be proven secure assuming block cipher is a PRP and random IVs are used
Important Requirements:

  • Choose random IV for each encryption
  • Protect integrity of IV (should be included in authentication)
  • Still does not guarantee integrity by itself

CBC Security Example: Diebold Voting Machines

Critical Error Found in Source Code:

DesCBCEncrypt((des_c_block*)tmp, (des_c_block*)record.m_Data, 
               totalSize, DESKEY, NULL, DES_ENCRYPT)

The NULL parameter means no IV was used!
This completely breaks CBC security (reduces to ECB mode).

Counter (CTR) Mode

Operation

Concept: Use block cipher to construct a PRNG

  • Start with a random counter value
  • yᵢ = Ekey[counter + i]
  • Cᵢ = Pᵢ ⊕ yᵢ (encryption)
  • Pᵢ = Cᵢ ⊕ yᵢ (decryption)

Shared between sender and receiver: Counter (does not need to be secret) and secret key

Performance Measures

Property CTR Mode CBC Mode
Encryption Parallelizable ✓ Yes ✗ No
Decryption Parallelizable ✓ Yes ✓ Yes
Random Read Access ✓ Yes ✗ No

Comparison: ECB vs CBC

Visual Demonstration:
When encrypting an image:

  • AES in ECB mode: Similar plaintext blocks produce similar ciphertext blocks – the outline of the image remains visible!
  • AES in CBC mode: Output looks completely random – no discernible patterns

Lesson: ECB mode preserves patterns in data, making it unsuitable for most applications

Importance of Randomness

Real-World Security Failures:

  • 2012: Flaw found in online encryption systems due to poor random number generation
  • Study: “Four of every 1,000 public keys provide no security” due to insufficient randomness

Takeaway: Cryptographic security critically depends on high-quality randomness

2.4 Hash Functions

Motivation: Data Integrity and Source Authentication

The Problem:

  • Encryption does NOT protect data from modification by another party
  • Need a way to ensure data arrives in its original form
  • Need to verify data is coming from an authenticated source

Cryptographic Hash Functions

Definition and Properties

Hash Function: A function that maps a message of arbitrary length to an m-bit output

  • Input: Bit strings of any length
  • Output: n-bit string (fixed length)
  • Output Names: Fingerprint, message digest, hash
  • Nature: Lossy compression (many-to-one function)

Key Property

Collision: H(x) = H(x’) for some inputs x ≠ x’

Collisions must exist (pigeonhole principle), but finding them should be computationally infeasible

Randomness Property

  • H(x) should look “random”
  • Every bit should be (almost) equally likely to be 0 or 1
  • Changing one bit of input should change approximately half the output bits

Requirements for Cryptographic Hash Functions

Given a function h: X → Y, we say that h is:

1. Preimage Resistant (One-way)

Given y ∈ Y, it is computationally infeasible to find a value x ∈ X such that h(x) = y

2. Second Preimage Resistant (Weak Collision Resistant)

Given x ∈ X, it is computationally infeasible to find a value x’ ∈ X such that x’ ≠ x and h(x’) = h(x)

3. Collision Resistant (Strong Collision Resistant)

It is computationally infeasible to find two distinct values x, x’ ∈ X such that h(x) = h(x’)

Birthday Attack

Birthday Paradox Application:
It is possible to find a collision of a hash function in 2n/2 operations, where 2n is the classical preimage resistance security
Birthday Paradox Example:

  • In a classroom of 30 students
  • Probability that at least one student shares YOUR birthday: ~7.9%
  • Probability that ANY two students share A birthday: ~70%!

Implication for Hash Functions:
A hash function with n-bit output needs n ≥ 256 to provide 128-bit collision resistance

Applications of Hash Functions

Application 1: Password Hashing

System Design:

  • Instead of storing user passwords, store hash(password)
  • When user enters password, compute its hash and compare
  • System does not store actual passwords!
  • Assumes adversary cannot go from hash to password (one-wayness)

Why Hashing is Better Than Encryption for Passwords

  • No decryption key to protect
  • Even if hash database is stolen, passwords remain protected (if strong)
  • One-way nature prevents reconstruction
Weakness: Passwords are not random and thus guessable!

Solution: Use salt
Store: {salt, Hash(salt, password)}

Salt prevents precomputed rainbow table attacks and ensures same passwords have different hashes

Application 2: Software Integrity

Scenario: Software manufacturer wants to ensure executable file is received without modification

  1. Manufacturer sends file to users
  2. Manufacturer publishes hash in trusted medium (e.g., New York Times)
  3. User downloads file and computes hash
  4. User compares computed hash with published hash
  5. If they match, file is authentic

Goal: Integrity, not secrecy
Property Needed: Given goodFile and hash(goodFile), very hard to find badFile such that hash(goodFile) = hash(badFile)

Which Hash Property is Needed?

Application Property Needed Reasoning
Password Storage One-wayness Hard to recover password from hash. But passwords are guessable, so use salt!
Software Integrity Full collision resistance Software images are not random. Vulnerable to chosen-prefix collision attacks
Chosen-Prefix Collision Attack:
Attacker can choose two arbitrarily different documents, then append different calculated values such that the whole documents have equal hash values

Given two different prefixes p₁, p₂, the attack finds two appendages m₁ and m₂ such that:
hash(p₁ || m₁) = hash(p₂ || m₂)

Well-Known Hash Functions

Hash Function Output Size Status
MD5 128 bits ❌ BROKEN – collision resistance completely broken
SHA-1 160 bits ⚠️ VULNERABLE – collision found in 2017, one-wayness still holds
SHA-2 Family 224, 256, 384, 512 bits ✓ SECURE – currently recommended
SHA-3 (Keccak) Variable ✓ SECURE – selected by NIST competition

SHA-3 Selection Process

  • NIST organized a competition for new standard hash algorithms
  • Selected: Keccak, designed by Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche

Limitation of Using Hash for Authentication

Problem: Requires an authentic channel to transmit the hash

  • Anyone can compute the hash of a message (hash function is public)
  • Adversary could replace both message and hash
  • Authentic channel not always possible

Solution Preview: Use a key to compute the hash → Message Authentication Code (MAC)

2.5 MAC and Authenticated Encryption

Message Authentication Code (MAC)

MAC Scheme: A hash family used for message authentication

  • Computation: MAC = CK(M)
  • Shared Secret: The sender and receiver share key K
  • Transmission: Sender sends (M, CK(M))
  • Verification: Receiver receives (X, Y) and verifies that CK(X) = Y

Security Property

To be secure: An adversary should not be able to come up with (X’, Y) such that CK(X’) = Y without knowing the key K

Provides: Both integrity and authentication – only someone who knows the key can compute correct MAC for a given message

MAC Operation Illustrated

Communication Flow:

  1. Alice: Has message and shared key K₁, K₂
  2. Alice computes: MAC = HMAC(K₂, message)
  3. Alice sends: (message, MAC)
  4. Adversary: Can observe but cannot forge valid MAC without key
  5. Bob receives: (message, MAC)
  6. Bob computes: HMAC(K₂, message) using his copy of K₂
  7. Bob verifies: Computed MAC = Received MAC?
  8. If match: Message is authentic and unmodified

HMAC (Hash-based MAC)

Design and Properties

HMAC: Constructs MAC from a cryptographic hash function

  • Invented by Bellare, Canetti, and Krawczyk (1996)
  • Used in SSL/TLS, mandatory for IPsec

Why HMAC Over Encryption?

  • Hashing is faster than encryption
  • Library code for hash functions widely available
  • Can easily replace one hash function with another
  • Historically, there were US export restrictions on encryption

Security Status

If used with a secure hash function (e.g., SHA-256) and according to specification (correct key size, correct output usage), no known practical attacks against HMAC

Combining Encryption and Authentication

Question: How should we combine encryption and MAC to achieve both confidentiality and integrity?

Three Approaches

Approach Operation Used In Security
Authenticate-then-Encrypt (AtE) a = MAC(x)
C = E(x, a)
Send: C		 SSL/TLS ⚠️ Not always secure
Encrypt-then-Authenticate (EtA) C = E(x)
a = MAC(C)
Send: (C, a)		 IPsec ✓ Secure
Encrypt-and-Authenticate (E&A) C = E(x)
a = MAC(x)
Send: (C, a)		 SSH ❌ Not secure

Why Encryption Alone is Insufficient

Key Insight: If an adversary can manipulate a ciphertext such that the observable behavior (success or failure of decryption) differs depending on the content of plaintext, then information about plaintext can be leaked

Defense: Authenticate ciphertext, and only decrypt after verifying ciphertext has not changed

Encrypt-then-Authenticate (EtA) is Secure

Why EtA Works:

  • C = E(x), a = MAC(C), transmit (C, a)
  • Receiver first verifies MAC before any decryption
  • No information leakage through decryption failures
  • MAC computed on ciphertext provides strong binding

Why AtE and E&A Are Insecure

Authenticate-then-Encrypt (AtE) Vulnerability

Problem:

  • a = MAC(x), C = E(x, a), transmit C
  • First step is decryption – its success or failure may leak information
  • Reason: MAC is verified only AFTER decryption
  • Famous Attack: Decryption oracle attacks on TLS/SSL

Encrypt-and-Authenticate (E&A) Vulnerability

Problem:

  • C = E(x), a = MAC(x), transmit (C, a)
  • MAC has no guarantee for confidentiality
  • MAC is deterministic: messages are equal ⇒ their MACs are equal
  • Result: Breaks chosen-plaintext security

Detailed E&A Attack Scenario

Attack on Encrypt-and-Authenticate:

  1. Alice encrypts msg: Encrypt(K₁, msg)
  2. Alice computes MAC: MAC = HMAC(K₂, msg)
  3. Alice sends: (encrypt(msg), MAC(msg))
  4. Later, Alice sends another message msg2
  5. Adversary observes: If MAC(msg) = MAC(msg2), then msg = msg2!
  6. Result: Adversary can tell if messages are the same

Why this breaks security:

  • MAC is deterministic: equal messages → equal MACs
  • This violates ciphertext indistinguishability
  • Breaks chosen-plaintext security

Solutions and Best Practices

Recommended Approach: Encrypt, then MAC

Alternative (Also Secure): MAC, then Encrypt

Important Details:

  • Do not forget to include IV in MAC computation
  • Use separate keys for encryption and MAC (K₁ ≠ K₂)
  • If encryption is malleable, attacks are possible even with MAC
Critical Warning: Very dangerous if encryption is malleable. We will see specific attacks later in the course.

Principles of Cryptographic Design

Core Principles

1. Arbitrary Adversary Principle
Assume restrictions on adversary’s computational capabilities, NOT on adversary’s strategy!

2. Kerckhoff’s Principle
Keys can be secret, design is public

3. Sufficient Key Length Principle
Number of possible keys should be large enough to make attacks infeasible using best adversary resources expected during sensitivity period of data

4. Limited Key Usage Principle
Refresh keys, use master key-session key combinations

5. Modular Design
Design and analyze simple functions, use them to construct stronger functions in modular ways

6. Well-Defined, Conservative Assumptions
Use well-defined, conservative assumptions and security models

Summary: Key Takeaways

Module 2 Key Lessons:

  1. Cryptography Goals: Confidentiality and Integrity/Authentication
  2. Perfect Secrecy: One-Time Pad achieves it but impractical (key length = message length)
  3. Stream Ciphers: Fast but vulnerable to key reuse and malleability
  4. Block Ciphers: AES is current standard; mode of operation matters (CBC > ECB)
  5. Hash Functions: Provide integrity; need collision resistance for security
  6. MACs: Provide authentication and integrity; HMAC is standard
  7. Authenticated Encryption: Encrypt-then-MAC is the secure approach
  8. Security Models: Design for chosen-plaintext security minimum